package BackTracking.segmentation;//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
//
// 回文串 是正着读和反着读都一样的字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aab"
//输出：[["a","a","b"],["aa","b"]]
// 
//
// 示例 2： 
//
// 
//输入：s = "a"
//输出：[["a"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 16 
// s 仅由小写英文字母组成 
// 
// Related Topics 字符串 动态规划 回溯 👍 850 👎 0


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class partition {

    List<List<String>> res = new ArrayList<>();
    Deque<String> deque = new ArrayDeque<>();
    public List<List<String>> partition(String s) {

        int len = s.length();
        //做一次动态规划来存储是否是回文串，dp[i][j]的值表示i-j的子串是否为回文
        boolean[][] dp = new boolean[len][len];
        //初始化 对角线肯定是回文
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        char[] chars = s.toCharArray();
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                // 如果两头的字符不相等,则一定不是回文串
                if (chars[i]!=chars[j]){
                    dp[i][j] = false;
                }else{
                    //此时两头相等，但是如果头尾去掉以后没有字符剩余，或者剩下一个字符的时候，肯定是回文串
                    //即(j-1)-(i+1) + 1 < 2   =  j-i<3
                    if(j-i<3){
                        dp[i][j] = true;
                    }else{
                        // 状态转移
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
            }
        }
        // 然后回溯时则利用这个动态规划矩阵检查是否是回文
        dfs(s,0,len-1,dp);
        return res;
    }

    void dfs(String s, int start, int end, boolean[][] dp){

        if(start>end){
            //如果当前遍历到末尾，说明完成一次
            res.add(new ArrayList<>(deque));
            return;
        }

        for(int len = 1; len<= (end-start+1); len++){
            //如果当前截取的字符串不是回文串，则跳过
            if(!dp[start][start+len-1]){
                continue;
            }
            deque.add(s.substring(start, start+len));
            dfs(s,start+len,end,dp);
            deque.removeLast();
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
